package first

import "gitee.com/themoonstone/toOffer/first/original"

/*
	定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
	示例:

	输入: 1->2->3->4->5->NULL
	输出: 5->4->3->2->1->NULL

	限制：

	0 <= 节点个数 <= 5000

	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof
	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func ReverseList(head *original.ListNode) *original.ListNode {
	return reverseList(head)
}
func reverseList(head *original.ListNode) *original.ListNode {
	if nil == head {
		return nil
	}
	if nil == head.Next {
		return head
	}

	ret := reverseList(head.Next)
	head.Next.Next = head
	head.Next = nil
	return ret
}

func reverseList2(head *original.ListNode) *original.ListNode {
	if nil == head || nil == head.Next {
		return head
	}
	var pre *original.ListNode
	cur := head
	for nil != cur {
		next := cur.Next
		cur.Next = pre
		pre = cur
		cur = next
	}
	return pre
}
